package main

import "fmt"

/*
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

*/

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

type ListNode struct {
	Val  int
	Next *ListNode
}

func reverseKGroup(head *ListNode, k int) *ListNode {
	hair := &ListNode{Next: head}
	lastTail := hair // 上一组的尾节点

	for head != nil {
		tail := lastTail
		// tail 往后走k步，找到需要反转的尾节点
		for i := 0; i < k; i++ {
			tail = tail.Next
			if tail == nil { // 不足k个节点不反转
				return hair.Next
			}
		}
		nex := tail.Next // 下一组的头
		tail.Next = nil  // 断开tail，避免反转时多遍历节点
		head, tail = reverse(head, tail)
		lastTail.Next = head // 头链接
		tail.Next = nex      // 尾链接
		lastTail = tail      // 更新上一组的尾节点
		head = nex           // 更新下一组的开始
	}
	return hair.Next
}

func reverse(head, tail *ListNode) (*ListNode, *ListNode) {
	t := head
	h := &ListNode{}
	p := head
	for p != nil {
		temp := p
		p = p.Next
		temp.Next = h.Next
		h.Next = temp
	}
	return h.Next, t
}

func main() {
	nodeList := []*ListNode{
		&ListNode{Val: 1},
		&ListNode{Val: 2},
		&ListNode{Val: 3},
		&ListNode{Val: 4},
		&ListNode{Val: 5},
	}
	for i := 0; i < len(nodeList)-1; i++ {
		nodeList[i].Next = nodeList[i+1]
	}
	k := 2
	node := reverseKGroup(nodeList[0], k)
	for node != nil {
		fmt.Print(node.Val, " ")
		node = node.Next
	}
}
